import java.util.*;

/**
 * @(#) Validator.java
 */
public class Validator
{
    /*
    Main validation method, call all other methods from here
     */
	public boolean validateChart( Collection tasks )
	{
		return  hasOneStartNode ( tasks )
            && hasOneEndNode ( tasks )
            && isACyclic ( tasks )
            && hasNoUnlinkedNodes ( tasks )
        ;
	}

    /*
    Check that there is a single node without predecessors
     */
	public boolean hasOneStartNode( Collection tasks )
	{
        Integer counter = 0;

        for ( Task task:(ArrayList<Task>)tasks ) {
            if ( task.getPredecessors().size() == 0 ) {
                counter ++;
            }
        }

        if ( counter == 0 ) {
            System.out.println( "[hasOneStartNode] There are no start nodes." );
            return false;
        }
        else if ( counter > 1 ) {
            System.out.println ( "[hasOneStartNode] There is more than 1 start node." );
            return false;
        }
		return true;
	}

    /*
    Check that there is a single node without successors
     */
	public boolean hasOneEndNode( Collection tasks )
	{
        Set<Task> predecessors = new TreeSet<Task>();

        for ( Task task:(ArrayList<Task>)tasks ) {

            predecessors.addAll((ArrayList<Task>) task.getPredecessors());
        }

        Integer counter = 0;

        for ( Task task:(ArrayList<Task>)tasks ) {
            if ( ! predecessors.contains ( task ) ) {
                counter ++;
            }
        }

        if ( counter == 0 ) {
            System.out.println( "[hasOneEndNode] There are no end nodes." );
            return false;
        }
        else if ( counter > 1 ) {
            System.out.println ( "[hasOneEndNode] There is more than 1 end node." );
            return false;
        }
        return true;
	}

    /*
    Check that the graph is acyclic
     */
	public boolean isACyclic( Collection tasks )
	{
		//TODO better algorithm

//        Iterator i = l.begin(), j = l.begin();
//        while (true) {
//            // increment the iterators, if either is at the end, you're done, no circle
//            if (i.hasNext())  i = i.next(); else return false;
//
//            // second iterator is travelling twice as fast as first
//            if (j.hasNext())  j = j.next(); else return false;
//            if (j.hasNext())  j = j.next(); else return false;
//
//            // this should be whatever test shows that the two
//            // iterators are pointing at the same place
//            if (i.getObject() == j.getObject()) {
//                return true;
//            }
//        }
        Set<Task> allNodePredecessors;
        ArrayList<Task> nodePredecessors;

        LinkedList<Task> queue;
        Task subtask;
        Integer cycle_counter = 0;

        for ( Task task:(ArrayList<Task>)tasks ) {

            queue = new LinkedList<Task>();
            cycle_counter = 0;

            queue.push ( task );

            allNodePredecessors    = new TreeSet<Task>();

            while ( ! queue.isEmpty() )
            {
                subtask = queue.pollFirst ();

                nodePredecessors = (ArrayList<Task>)subtask.getPredecessors();
                allNodePredecessors.addAll ( nodePredecessors );

                if ( allNodePredecessors.contains ( task ) || allNodePredecessors.contains ( subtask )) {
                    cycle_counter ++;
                }

                if ( cycle_counter > 1e6 ) {
                    System.out.println ( "[isACyclic] There is a cycle." );
                    return false;
                }

                queue.addAll ( nodePredecessors );
            }
        }
        return true;
	}

    /*
    Check that each node has at least 1 successor or predecessor
     */
	public boolean hasNoUnlinkedNodes( Collection tasks )
	{
        Set<Task> predecessors = new TreeSet<Task>();
        Set<Task> nodePredecessors;

        for ( Task task:(ArrayList<Task>)tasks ) {

            nodePredecessors    = new TreeSet<Task> ( (ArrayList<Task>)task.getPredecessors() );
            nodePredecessors.remove ( task );

            predecessors.addAll ( nodePredecessors );
        }

//        Calc all single nodes w/o self cycle
        nodePredecessors    = new TreeSet<Task>( (ArrayList<Task>) tasks );
        nodePredecessors.removeAll ( predecessors );

        Integer singleNodes = nodePredecessors.size();

        if ( singleNodes == 0 ) {
            System.out.println( "[hasNoUnlinkedNodes] There are 0 unlinked nodes." );
            return false;
        }
        else if ( singleNodes > 1 ) {
            System.out.println ( "[hasNoUnlinkedNodes] There is more than 1 single node." );
            return false;
        }

		return true;
	}
}
